﻿using System;

namespace Eratosthenes
{
    class Program
    {
        static void Main(string[] args)
        {
            const int MaxSize = 65535;
            int p = 0;
            int[] prime = new int[MaxSize];//记录素数
            bool[] IsPrime = new bool[MaxSize];//记录是否是素数，索引对应对应的数
            for (int i = 0; i <= 100; i++)
                IsPrime[i] = true;//初始化
            IsPrime[0] = false;
            IsPrime[1] = false;//0,1不是素数
            for(int i = 2; i <= 100; i++)//埃氏筛法
            {
                if (IsPrime[i])//2本身是素数
                {
                    prime[p] = i;//记录素数和素数个数
                    p++;
                    for (int k = i * 2; k <= 100; k = k + i)//筛法，去掉2的倍数(数组标记false)，for循环让其之后继续去掉3的倍数，5的倍数，7的倍数……（中间的数已经被筛掉），最后剩下的数为素数且已经记录到Prime[]
                        IsPrime[k] = false;
                }
            }
            Console.WriteLine("The number of prime from 2 to 100:" + p);
            for(int i = 0; i < p; i++)
            {
                Console.WriteLine(prime[i]);
            }
        }
    }
}
